﻿#pragma once

#include<vector>

namespace bit
{
	//仿函数的类
	template<class T>            //由于此处仿函数需要实现两个数的比较，因此此处需要模板参数T
	class less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	// 特化 - 偏特化                           // 注意，特化必须要存在原模板，不然err
	template<class T>         //注意，此处不能写成template<> ，因为此处为走限制的特化，需要表明模板参数T
	class less<T*>       //此处T* 表明，只要是指针类型传进来，那么都会走这个偏特化，即仿函数的偏特化实现了对所传参数的限制
	{                    //如果传进来int* ，那么T 则是int ，这是为了可以更好地使用所传指针的原类型
	public:
		//bool operator()(T* & x, T* & y)                  //这样也是可以的      //特别注意：特化中的const，如果不注意会是一个坑
		bool operator()(const T* const& x, const T* const& y)      //注意，此处情况下必须是T* ，不能只写T，因为只有T* 才是指针，而T 只是一个类型，无法在下边的比较中去解引用T，只能解引用T*
		{
			return *x < *y;
		}
	};

	template<class T>
	class greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};





	//实现优先队列
	template<class T, class Container = vector<T>, class Compare = less<T>>         //此处在优先队列类型已经使用了模板的参数Compare ，并给到缺省值为less
	class priority_queue
	{
	public:
		priority_queue()
		{
		}

		void push(const T& x)         //入堆，先尾插，后向上调整算法
		{
			_con.push_back(x); 

			adjustup(_con.size() - 1);
		}

		void pop()                  //先交换至队尾出数据，再向下调整算法
		{
			swap(_con[0], _con[_con.size() - 1]); 
			_con.pop_back(); 

			adjustdown(0);
		}

		const T& top() const
		{
			return _con[0];
		}

		bool empty() const
		{
			return _con.empty();
		}

		size_t size() const
		{
			return _con.size();
		}

	private:
		void adjustup(int child)
		{
			Compare com;                                //由于前面模板参数中有class Compare ，因此Compare 是一个类型，而此处的com ，就是Compare 这个类型实例化的对象，即仿函数
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))            //使用仿函数
				{
					swap(_con[child], _con[parent]);

					// 
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void adjustdown(size_t parent)
		{
			Compare com;                             //同上

			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))            //此处先保证右孩子存在再比较，而由于是完全二叉树，因此右孩子不存在时，此结点一定到了最后一个结点处
				{
					++child;
				}

				//if (_con[parent] < _con[child])
				if (com(_con[parent], _con[child]))             //同上
				{
					swap(_con[child], _con[parent]);

					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	private:
		Container _con;                //上面模板参数中有class Container ，因此此处Container 是一个类，那么_con 就是该类的对象
	};
}
